package quicksort

func partition(nums []int, left int, right int) int {
    value := nums[left]
    for left < right {
        for nums[right] >= value && left < right {
            right--
        }
        nums[left] = nums[right]
        for nums[left] < value && left < right {
            left++
        }
        nums[right] = nums[left]
    }
    nums[left] = value
    return left
}

func QuickSort(list []int, left int, right int) []int {

    if left < right {
        middle := partition(list, left, right)
        QuickSort(list, left, middle-1)
        QuickSort(list, middle+1, right)
    }
    
    return list
}


